package editingDistance;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.TreeSet;



import gettree.TreeNode;

public class Algorithm {
	public static HashMap<Integer, TreeNode> ptmap ;
	public static HashMap<TreeNode, Integer> invptmap;
	public static ArrayList<Integer> pt_lr_keyR;

	public static HashMap<Integer, TreeNode> astmap ;
	public static HashMap<TreeNode, Integer> invastmap;
	public static ArrayList<Integer> ast_lr_keyR;

	private static double[][] distance = null;

	public static double doWork(TreeNode pt , TreeNode ast){
		ConstructHashMap.dowork(pt);
		ptmap=ConstructHashMap.map;
		invptmap = ConstructHashMap.inverseMap;
		pt_lr_keyR = ConstructHashMap.LR_keyroots;

		ConstructHashMap.dowork(ast);
		astmap=ConstructHashMap.map;
		invastmap = ConstructHashMap.inverseMap;
		ast_lr_keyR = ConstructHashMap.LR_keyroots;
		distance = new double [ptmap.size()+1][astmap.size()+1];
		int i ; 
		int j ; 
		for (int ip = 0 ; ip< pt_lr_keyR.size();ip++){
			for (int jp= 0 ; jp<ast_lr_keyR.size();jp++){
				i=pt_lr_keyR.get(ip);
				j=ast_lr_keyR.get(jp);
				Hashtable<Integer, Hashtable<Integer, Double>> fD = 
						new Hashtable<Integer, Hashtable<Integer, Double>>();
				setFD(ptmap.get(i).getLi(),astmap.get(j).getLi(),0.0d,fD);

				for (int k = ptmap.get(i).getLi() ; k <= i;k++){
					// 1 de la delete
					setFD(k,astmap.get(j).getLi()-1,getFD(k-1,astmap.get(j).getLi()-1,fD)+1,fD);
					//seeFD(k,astmap.get(j).getLi()-1,fD);
				}

				for (int k = astmap.get(j).getLi() ; k <= j ;k++){
					// 1 de la insert
					setFD(ptmap.get(i).getLi()-1,k,getFD(ptmap.get(i).getLi()-1,k-1,fD)+1,fD);
					//seeFD(ptmap.get(i).getLi()-1,k,fD);
				}

				//System.out.println("BEFORE cross checks: ");
				//seeFD(fD);


				for (int i1 = ptmap.get(i).getLi() ; i1 <= i ; i1++)
					for(int j1 = astmap.get(j).getLi() ; j1<=j;j1++  ){
						double min = java.lang.Math.min(
								//delete
								getFD(i1-1,j1,fD)+1,
								//insert
								getFD(i1,j1-1,fD)+1
								);
						String d ;
						if (min == getFD(i1-1,j1,fD)+1)
							d="delete " + i1  + " " + j1;
						else
							d="insert " + i1  + " " + j1;
						if (ptmap.get(i1).getLi() == ptmap.get(i).getLi() && astmap.get(j1).getLi()==astmap.get(j).getLi()){
							distance[i1][j1] = java.lang.Math.min(
									min,
									// remane
									getFD(i1-1,j1-1, fD)+(ptmap.get(i1).getLabel().equals(astmap.get(j1).getLabel())?0:1)
									);
							setFD(i1, j1, distance[i1][j1], fD);
							//System.out.println("i:" +i1+ "j:" + j1 +" "+ d);
						//	seeFD(i1,j1, fD);
						}
						else {
							setFD(i1,j1,
									java.lang.Math.min(
											min,
											getFD(ptmap.get(i1).getLi()-1,astmap.get(j1).getLi()-1,fD)+distance[i1][j1]),
											fD
									);
					//		seeFD(i1,j1,fD);
							
						}
						
					}
				
				//seeFD(fD);
			}
		}
		//System.out.println(distance[ptmap.size()][astmap.size()]);
		for (int q= 0 ;  q <ptmap.size()+1;q++ )
		{
			//System.out.println();
			for (int w =0 ; w<astmap.size()+1;w++);
				//System.out.print(distance[q][w] + " ");
			
		}
		return distance[ptmap.size()][astmap.size()];
	}

	/** This returns the value in the cell of the ForestDistance table
	 */
	private static double getFD(int a, int b,
			Hashtable<Integer, Hashtable<Integer,Double>> 
	forestDistance) {

		Hashtable<Integer, Double> rows = null;
		if (!forestDistance.containsKey(a)) {
			//  	    System.out.println("getFD: creating new aStr entry.");
			forestDistance.put(a, new Hashtable<Integer, Double>());
		}

		rows = forestDistance.get(a);
		if (!rows.containsKey(b)) {
			// 	    System.out.println("creating new bStr entry.");
			rows.put(b, 0.0);
		}
		return rows.get(b);
	}

	/** This sets the value in the cell of the ForestDistance table
	 */
	private static  void setFD(int a, int b,
			double aValue, 
			Hashtable<Integer, Hashtable<Integer,Double>> 
	forestDistance ) {

		Hashtable<Integer, Double> rows = null;
		if (!forestDistance.containsKey(a)) {
			forestDistance.put(a, new Hashtable<Integer, Double>());
		}
		rows = forestDistance.get(a);
		rows.put(b, aValue);
	}


	private static void seeFD(Hashtable<Integer, Hashtable<Integer,Double>> 
	forestDistance) {
		//System.out.println("Forest Distance");
		//Return result
		for (Integer i : new TreeSet<Integer>(forestDistance.keySet())) {
			//System.out.print(i+": ");
			for (Integer j : new TreeSet<Integer>(forestDistance.get(i).keySet())) {
				//System.out.print(forestDistance.get(i).get(j)+"("+j+")  ");
			}
			//System.out.println("");
		}
	}

	private static  void seeFD(int a, int b,
			Hashtable<Integer, Hashtable<Integer,Double>> 
	forestDistance) {

		//System.out.println("["+a+"],["+b+"]: "+getFD(a,b,forestDistance));
	}


	public static void main (String [] a){
		TreeNode node = new TreeNode(null, "1", null);
		TreeNode node2 = new TreeNode(null, "2", null);
		TreeNode node3 = new TreeNode(null, "3", null);
		TreeNode node4 = new TreeNode(null, "4", null);
		TreeNode node5 = new TreeNode(null, "5", null);
		TreeNode node6 = new TreeNode(null, "6", null);
		TreeNode node7 = new TreeNode(null, "7", null);
		TreeNode node8 = new TreeNode(null, "8", null);
		TreeNode node9 = new TreeNode(null, "9", null);
		TreeNode node10 = new TreeNode(null, "10", null);
		TreeNode node11 = new TreeNode(null, "11", null);
		TreeNode node12 = new TreeNode(null, "12", null);
		node.addChild(node2);
		node.addChild(node3);
		node.addChild(node4);
		node2.addChild(node5);
		node3.addChild(node6);
		node3.addChild(node7);
		node4.addChild(node8);
		node8.addChild(node9);
		node8.addChild(node10);
		node10.addChild(node11);
		node10.addChild(node12);

		TreeNode node_ = new TreeNode(null, "1", null);
		TreeNode node2_ = new TreeNode(null, "2", null);
		TreeNode node3_ = new TreeNode(null, "3", null);
		TreeNode node4_ = new TreeNode(null, "4", null);
		TreeNode node5_ = new TreeNode(null, "5", null);
		TreeNode node6_ = new TreeNode(null, "6", null);
		TreeNode node7_ = new TreeNode(null, "7", null);
		TreeNode node8_ = new TreeNode(null, "8", null);
		TreeNode node9_ = new TreeNode(null, "9", null);
		TreeNode node10_ = new TreeNode(null, "10", null);
		TreeNode node11_ = new TreeNode(null, "11", null);
		TreeNode node12_ = new TreeNode(null, "12", null);
		
		node_.addChild(node2_);
		node_.addChild(node4_);
		node_.addChild(node3_);
		node2_.addChild(node5_);
		node3_.addChild(node6_);
		node3_.addChild(node7_);
		node4_.addChild(node8_);
		node8_.addChild(node9_);
		node8_.addChild(node10_);
		node10_.addChild(node11_);
		node10_.addChild(node12_);
		
		System.out.println(doWork(node,node_));/*
		TreeNode node1 = new TreeNode(null, "unu", null);
		TreeNode node2 = new TreeNode(null, "doi", null);
		TreeNode node3 = new TreeNode(null, "trei", null);
		TreeNode node4 = new TreeNode(null, "patru", null);
		TreeNode node5 = new TreeNode(null, "cinci", null);
		TreeNode node6 = new TreeNode(null, "sase", null);
		TreeNode node7 = new TreeNode(null, "sapte", null);
		TreeNode node8 = new TreeNode(null, "opt", null);
		TreeNode node9 = new TreeNode(null, "noua", null);

		node9.addChild(node3);
		node9.addChild(node8);

		node3.addChild(node1);
		node3.addChild(node2);

		node8.addChild(node6);
		node8.addChild(node7);

		node6.addChild(node4);
		node6.addChild(node5);

		ConstructHashMap.dowork(node9);
		System.out.println(ConstructHashMap.map);

		System.out.println("ML:");
		for (Integer u : ConstructHashMap.map.keySet()){
			System.out.println(u + "("+ConstructHashMap.map.get(u).getLabel()+")"+ "->" + ConstructHashMap.map.get(u).getLi() +"("+ConstructHashMap.map.get(ConstructHashMap.map.get(u).getLi()).getLabel()+")");
		}

		System.out.println("key:");
		for (Integer u : ConstructHashMap.LR_keyroots){
			System.out.println(u);
		}*/


	}
}



